<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>重复或者缺失的数字</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="重复或者缺失的数字">重复或者缺失的数字</h1>
<h1 id="1-在数组中有1个数只出现一次其他数均出现两次问怎样快速找出这1个数">1. 在数组中有1个数只出现一次，其他数均出现两次。问怎样快速找出这1个数。</h1>
<p>hashtabel   时间复杂度 O(n), 空间复杂度 O(n)</p>
<p>异或 时间复杂度O(n), 空间复杂度O(1)</p>
<h2 id="lc-540-single-element-in-a-sorted-array-如果是数组已经排序了可以用二分查找">LC 540. Single Element in a Sorted Array 如果是数组已经排序了，可以用二分查找</h2>
<ul>
<li><a href="https://leetcode.com/problems/single-element-in-a-sorted-array/">https://leetcode.com/problems/single-element-in-a-sorted-array/</a></li>
</ul>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">singleNonDuplicate</span><span class="hljs-params">(self, nums: List[int])</span> -&gt; int:</span>
        n = len(nums)
        left = <span class="hljs-number">0</span>
        right = len(nums)

        
        <span class="hljs-keyword">while</span> left &lt; right:
            mid = (left + right) // <span class="hljs-number">2</span>
            <span class="hljs-keyword">if</span> mid % <span class="hljs-number">2</span> == <span class="hljs-number">0</span>:
                <span class="hljs-keyword">if</span> mid == n - <span class="hljs-number">1</span>:      <span class="hljs-comment">#针对 [1,1,2] 或者[1]的情况。防止数组越界</span>
                    <span class="hljs-keyword">return</span> nums[mid]

                <span class="hljs-keyword">if</span> nums[mid] == nums[mid+<span class="hljs-number">1</span>]:
                    left = mid + <span class="hljs-number">1</span>
                <span class="hljs-keyword">else</span>:
                    right = mid
            <span class="hljs-keyword">else</span>:
                <span class="hljs-keyword">if</span> nums[mid] == nums[mid<span class="hljs-number">-1</span>]:
                    left = mid + <span class="hljs-number">1</span>
                <span class="hljs-keyword">else</span>:
                    right = mid
        <span class="hljs-keyword">return</span> nums[left]
    
    
</div></code></pre>
<h1 id="2-在数组中有2个数只出现一次其他数均出现两次问怎样快速找出这两个数">2. 在数组中有2个数只出现一次，其他数均出现两次。问怎样快速找出这两个数。</h1>
<p>LC 260. Single Number III</p>
<ul>
<li><a href="https://leetcode.com/problems/single-number-iii/">https://leetcode.com/problems/single-number-iii/</a></li>
</ul>
<p>Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.</p>
<pre><code><code><div>Example:

Input:  [1,2,1,3,2,5]
Output: [3,5]
Note:

The order of the result is not important. So in the above example, [5, 3] is also correct.
Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?
</div></code></code></pre>
<h2 id="1常规解法">1.常规解法</h2>
<p>1、将数组中所有元素进行异或操作，因为相同的数异或为0，这样得到的结果就是a异或b的值。</p>
<p>2、因为a和b肯定不相等，所以第一步得到的结果肯定不为0.也就是说此结果写成二进制至少有一位是1，找到这个为1的下标。用这一位我们可以把数组中的数分成两部分，一部分是这一位为1的数，一部分是这一位为0的数。a和b肯定不在同一个部分。数组中原来相同的数肯定在同一个部分。</p>
<p>3、将这两部分数分别进行异或运算。最后每部分异或的结果就是a和b。</p>
<p>时间复杂度：O(n)</p>
<p>空间复杂度：O(1)</p>
<pre><code class="language-c++"><div><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;iostream&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;vector&gt;</span></span>
<span class="hljs-keyword">using</span> <span class="hljs-keyword">namespace</span> <span class="hljs-built_in">std</span>;
 
<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; FindTwoOnce(<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; num){
    <span class="hljs-keyword">if</span>(num.size()&lt;=<span class="hljs-number">2</span>)               <span class="hljs-comment">//对符合要求的num数组，只有两个元素则直接返回</span>
        <span class="hljs-keyword">return</span> num;
    <span class="hljs-keyword">int</span> res=<span class="hljs-number">0</span>;                      <span class="hljs-comment">//存储数组所有元素异或的结果</span>
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;num.size();i++){
        res ^= num[i];
    }
    <span class="hljs-keyword">int</span> index=<span class="hljs-number">0</span>;                    <span class="hljs-comment">//存储异或结果二进制表示中，从右往左第一个为1的下标</span>
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;<span class="hljs-number">32</span>;i++){
        <span class="hljs-keyword">int</span> temp=res;
        <span class="hljs-keyword">if</span>((temp&gt;&gt;i) &amp; <span class="hljs-number">1</span> == <span class="hljs-number">1</span>){     <span class="hljs-comment">//第i位为1</span>
            index=i;
            <span class="hljs-keyword">break</span>;
        }
    }
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; result;             <span class="hljs-comment">//存储问题结果的数组</span>
    result.push_back(<span class="hljs-number">0</span>);
    result.push_back(<span class="hljs-number">0</span>);
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;num.size();i++){
        <span class="hljs-keyword">if</span>((num[i]&gt;&gt;index) &amp; <span class="hljs-number">1</span> == <span class="hljs-number">1</span>)<span class="hljs-comment">//第i位是1的一类</span>
            result[<span class="hljs-number">0</span>] ^= num[i];
        <span class="hljs-keyword">else</span>                        <span class="hljs-comment">//第i位是0的一类</span>
            result[<span class="hljs-number">1</span>] ^= num[i];
    }
    <span class="hljs-keyword">return</span> result;
}
 
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>{
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; num;
    num.push_back(<span class="hljs-number">2</span>);
    num.push_back(<span class="hljs-number">2</span>);
    num.push_back(<span class="hljs-number">3</span>);
    num.push_back(<span class="hljs-number">4</span>);
    num.push_back(<span class="hljs-number">5</span>);
    num.push_back(<span class="hljs-number">5</span>);
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; result=FindTwoOnce(num);
    <span class="hljs-built_in">cout</span>&lt;&lt;result[<span class="hljs-number">0</span>]&lt;&lt;<span class="hljs-string">' '</span>&lt;&lt;result[<span class="hljs-number">1</span>]&lt;&lt;<span class="hljs-built_in">endl</span>;
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
}
</div></code></pre>
<h2 id="2-利用-x---x-用以提取倒数第一个非零位">2. 利用 x &amp; (-x) 用以提取倒数第一个非零位</h2>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">singleNumber</span><span class="hljs-params">(self, nums: List[int])</span> -&gt; List[int]:</span>
        diff = <span class="hljs-number">0</span>
        <span class="hljs-keyword">for</span> num <span class="hljs-keyword">in</span> nums:
            diff ^= num
            
        rightmostbit1 = diff &amp; (-diff)

        diff2 = <span class="hljs-number">0</span>
        <span class="hljs-keyword">for</span> num <span class="hljs-keyword">in</span> nums:
            <span class="hljs-keyword">if</span> num &amp; rightmostbit1 == rightmostbit1:  <span class="hljs-comment"># 注意，这里不能写成 num &amp; rightmostbit1 == 1</span>
                diff2 ^= num
                
        num1 = diff2
        num2 = diff ^ diff2
        <span class="hljs-keyword">return</span> [num1, num2]
</div></code></pre>
<p>关键的那个判断写成 if num &amp; rightmostbit1:  或者 if num &amp; rightmostbit1 == rightmostbit1 或者 if num &amp; rightmostbit1 ==0都行, 但不能写成 if num &amp; rightmostbit1 == 1：</p>
<h2 id="继续思考">继续思考：</h2>
<p>位操作可以在数组中找出只出现一次的一个元素；只出现一次的两个元素。那么数组中有三个元素只出现一次，其他元素都出现两次，用位操作运算可以找出这三个数吗？</p>
<p>答案是可以用位运算找出这三个数。</p>
<p>将数组中所有的数进行异或运算，最后得到的是abc异或的结果。对此结果找到为1的那一位，用此位对数组分成两类。必有一类它的数字个数是奇数。这一类可能同时包含abc，也可能只包含abc其中一个。如果只包含abc其中一个，那么问题就变成了数组中有一个数只出现一次、数组中有两个数只出现一次，问题解决了。如果同时包含abc，那么继续上面的操作直到得到一部分只包含abc其中一个为止，问题也解决了。</p>
<h1 id="3-在数组中有1个数只出现一次其他数均出现3次问怎样快速找出这两个数">3. 在数组中有1个数只出现一次，其他数均出现3次。问怎样快速找出这两个数。</h1>
<p>LC 137. 只出现一次的数字 II</p>
<p>解法1：  从0到31逐bit 求和sum(i),   t(i) = sum(i)%3  把t(i)拼接回去就是结果。</p>
<p><a href="https://zhuanlan.zhihu.com/p/78080075">https://zhuanlan.zhihu.com/p/78080075</a></p>
<pre><code class="language-java"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span> </span>{
<span class="hljs-keyword">public</span>:
    <span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">singleNumber</span><span class="hljs-params">(vector&lt;<span class="hljs-keyword">int</span>&gt;&amp; nums)</span> </span>{
        <span class="hljs-function">vector&lt;<span class="hljs-keyword">int</span>&gt; <span class="hljs-title">bit</span><span class="hljs-params">(<span class="hljs-number">32</span>, <span class="hljs-number">0</span>)</span></span>;
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j = <span class="hljs-number">0</span>; j &lt; <span class="hljs-number">32</span>; j++){
            <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; nums.size(); i++){
                bit[j] += nums[i] &gt;&gt; j &amp; <span class="hljs-number">1</span>;
            }
        }
        <span class="hljs-keyword">int</span> res = <span class="hljs-number">0</span>;
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">31</span>; i &gt;= <span class="hljs-number">0</span>; i--){
            res &lt;&lt;= <span class="hljs-number">1</span>;
            res += bit[i] % <span class="hljs-number">3</span>;
        }
        <span class="hljs-keyword">return</span> res;
    }
};
</div></code></pre>
<p>解法2： <a href="https://zhuanlan.zhihu.com/p/113846542">https://zhuanlan.zhihu.com/p/113846542</a></p>
<p>很难想到…</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">singleNumber</span><span class="hljs-params">(self, nums: List[int])</span> -&gt; int:</span>
        seen_once = seen_twice = <span class="hljs-number">0</span>
        
        <span class="hljs-keyword">for</span> num <span class="hljs-keyword">in</span> nums:
            <span class="hljs-comment"># first appearance: </span>
            <span class="hljs-comment"># add num to seen_once </span>
            <span class="hljs-comment"># don't add to seen_twice because of presence in seen_once</span>
            
            <span class="hljs-comment"># second appearance: </span>
            <span class="hljs-comment"># remove num from seen_once </span>
            <span class="hljs-comment"># add num to seen_twice</span>
            
            <span class="hljs-comment"># third appearance: </span>
            <span class="hljs-comment"># don't add to seen_once because of presence in seen_twice</span>
            <span class="hljs-comment"># remove num from seen_twice</span>
            seen_once = ~seen_twice &amp; (seen_once ^ num)
            seen_twice = ~seen_once &amp; (seen_twice ^ num)

        <span class="hljs-keyword">return</span> seen_once
</div></code></pre>
<h1 id="4-lc-287-find-the-duplicate-number-某个数字重复多次">4. LC 287. Find the Duplicate Number  某个数字重复多次</h1>
<p><a href="https://leetcode.com/problems/find-the-duplicate-number/">https://leetcode.com/problems/find-the-duplicate-number/</a></p>
<p>Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.</p>
<pre><code><code><div>Example 1:
Input: [1,3,4,2,2]
Output: 2

Example 2:
Input: [3,1,3,4,2]
Output: 3

Note:
You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O(n2).
There is only one duplicate number in the array, but it could be repeated more than once.
</div></code></code></pre>
<p>这道题如果限定了重复的元素最多只会重复一次，也就是最多出现2次。那就非常简单。 sum(nums) - n*(n+1)//2 即可.  但因为可以出现多次，就变得复杂了。</p>
<p>这道题有2种解法。</p>
<h2 id="1-二分查找">(1) 二分查找</h2>
<p>This solution is based on binary search.</p>
<p>At first the search space is numbers between 1 to n. Each time I select a number mid (which is the one in the middle) and count all the numbers equal to or less than mid. Then if the count is more than mid, the search space will be [1 mid] otherwise [mid+1 n]. I do this until search space is only one number.</p>
<p>Let's say n=10 and I select mid=5. Then I count all the numbers in the array which are less than equal mid. If the there are more than 5 numbers that are less than 5, then by Pigeonhole Principle (<a href="https://en.wikipedia.org/wiki/Pigeonhole_principle">https://en.wikipedia.org/wiki/Pigeonhole_principle</a>) one of them has occurred more than once. So I shrink the search space from [1 10] to [1 5]. Otherwise the duplicate number is in the second half so for the next step the search space would be [6 10].</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span><span class="hljs-params">(object)</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">findDuplicate</span><span class="hljs-params">(self, nums)</span>:</span>
    <span class="hljs-string">"""
    :type nums: List[int]
    :rtype: int
    """</span>
    low = <span class="hljs-number">1</span>
    high = len(nums)<span class="hljs-number">-1</span>
    
    <span class="hljs-keyword">while</span> low &lt; high:
        mid = low+(high-low)/<span class="hljs-number">2</span>
        count = <span class="hljs-number">0</span>
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> nums:
            <span class="hljs-keyword">if</span> i &lt;= mid:
                count+=<span class="hljs-number">1</span>
        <span class="hljs-keyword">if</span> count &lt;= mid:
            low = mid+<span class="hljs-number">1</span>
        <span class="hljs-keyword">else</span>:
            high = mid <span class="hljs-comment"># 注意，这里一定是 high = mid, 不是 high = mid - 1, 因为mid可能就是我们要找的值</span>
    <span class="hljs-keyword">return</span> low
</div></code></pre>
<p>There's also a better algorithm with O(n) time. Please read this very interesting solution here:</p>
<p><a href="http://keithschwarz.com/interesting/code/?dir=find-duplicate">http://keithschwarz.com/interesting/code/?dir=find-duplicate</a></p>
<h2 id="2快慢指针">(2)快慢指针</h2>
<p>The main idea is the same with problem Linked List Cycle II,<a href="https://leetcode.com/problems/linked-list-cycle-ii/">https://leetcode.com/problems/linked-list-cycle-ii/</a>. Use two pointers the fast and the slow. The fast one goes forward two steps each time, while the slow one goes only step each time. They must meet the same item when slow==fast. In fact, they meet in a circle, the duplicate number must be the entry point of the circle when visiting the array from nums[0]. Next we just need to find the entry point. We use a point(we can use the fast one before) to visit form begining with one step each time, do the same job to slow. When fast==slow, they meet at the entry point of the circle. The easy understood code is as follows.</p>
<pre><code class="language-python"><div>int findDuplicate3(vector&lt;int&gt;&amp; nums)
{
	<span class="hljs-keyword">if</span> (nums.size() &gt; <span class="hljs-number">1</span>)
	{
		int slow = nums[<span class="hljs-number">0</span>];
		int fast = nums[nums[<span class="hljs-number">0</span>]];
		<span class="hljs-keyword">while</span> (slow != fast)
		{
			slow = nums[slow];
			fast = nums[nums[fast]];
		}

		fast = <span class="hljs-number">0</span>;
		<span class="hljs-keyword">while</span> (fast != slow)
		{
			fast = nums[fast];
			slow = nums[slow];
		}
		<span class="hljs-keyword">return</span> slow;
	}
	<span class="hljs-keyword">return</span> <span class="hljs-number">-1</span>;
}
</div></code></pre>
<p>上面的写法其实不好， 下面是我的写法，主要区别就在于初始值的设定。我固定设置为0。</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">findDuplicate</span><span class="hljs-params">(self, nums: List[int])</span> -&gt; int:</span>
        fast = <span class="hljs-number">0</span>
        slow = <span class="hljs-number">0</span>
        <span class="hljs-keyword">while</span> <span class="hljs-literal">True</span>:
            fast = nums[nums[fast]]
            slow = nums[slow]
            <span class="hljs-keyword">if</span> fast == slow:
                <span class="hljs-keyword">break</span>
        <span class="hljs-comment">#print(f"{fast} {nums[fast]}")</span>
        slow = <span class="hljs-number">0</span>
        <span class="hljs-keyword">while</span> fast != slow:
            fast = nums[fast]
            slow = nums[slow]
        <span class="hljs-keyword">return</span> fast
</div></code></pre>
<h1 id="5-lc-268-missing-number-缺失一个数字">5. LC 268. Missing Number   缺失一个数字</h1>
<ul>
<li><a href="https://leetcode.com/problems/missing-number/">https://leetcode.com/problems/missing-number/</a></li>
</ul>
<p>Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.</p>
<pre><code><code><div>Example 1:
Input: [3,0,1]
Output: 2
Example 2:
Input: [9,6,4,2,3,5,7,0,1]
Output: 8
</div></code></code></pre>
<h2 id="常规解法">常规解法</h2>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">missingNumber</span><span class="hljs-params">(self, nums: List[int])</span> -&gt; int:</span>
        n = len(nums)
        nums.sort()
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n):
            <span class="hljs-keyword">if</span> nums[i] != i:
                <span class="hljs-keyword">return</span> i
        <span class="hljs-keyword">return</span> n
</div></code></pre>
<p>利用hashtable来记录出现过的数字，再按照 0~n的顺序来查找谁没出现。 数据复杂和空间复杂度都是O(n)</p>
<p>数学解法</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">missingNumber</span><span class="hljs-params">(self, nums: List[int])</span> -&gt; int:</span>
        n = len(nums)
        <span class="hljs-keyword">return</span> n*(n+<span class="hljs-number">1</span>)//<span class="hljs-number">2</span> - sum(nums)
</div></code></pre>
<p>考虑到在c语言里面有可能溢出。 得这么写</p>
<pre><code><code><div>r = n
for i in range(n):
    r += i+1 - nums[i]
return r
</div></code></code></pre>
<p>Xor解法</p>
<pre><code><code><div>class Solution:
    def missingNumber(self, nums):
        missing = len(nums)
        for i, num in enumerate(nums):
            missing ^= i ^ num
        return missing
</div></code></code></pre>
<p>注意： 为什么missing的初始值是n.  参与异或的数值由两部分组成。</p>
<ol>
<li>0~n 的 n+1 个整数</li>
<li>nums 里面的n 个整数。</li>
</ol>
<p>异或完以后，最后的值就是缺失的number</p>
<h1 id="6-lc-645-set-mismatch-有一个数字出现2次同时有另一个数字缺失">6. LC 645. Set Mismatch  有一个数字出现2次，同时有另一个数字缺失</h1>
<ul>
<li><a href="https://leetcode.com/problems/set-mismatch/">https://leetcode.com/problems/set-mismatch/</a></li>
</ul>
<p>The set S originally contains numbers from 1 to n. But unfortunately, due to the data error, one of the numbers in the set got duplicated to another number in the set, which results in repetition of one number and loss of another number.</p>
<p>Given an array nums representing the data status of this set after the error. Your task is to firstly find the number occurs twice and then find the number that is missing. Return them in the form of an array.</p>
<pre><code><code><div>Example 1:
Input: nums = [1,2,2,4]
Output: [2,3]
Note:
The given array size will in the range [2, 10000].
The given array's numbers won't have any order.
</div></code></code></pre>
<p>用Counter来求解很简单。 如果要求O(1)的空间复杂度，就有点复杂. Labuladong 有一篇文章</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">findErrorNums</span><span class="hljs-params">(self, nums: List[int])</span> -&gt; List[int]:</span>
        len_nums = len(nums)
        i = <span class="hljs-number">0</span>
        ans = [<span class="hljs-number">0</span>, <span class="hljs-number">0</span>]
        <span class="hljs-keyword">while</span> i &lt; len_nums:
            <span class="hljs-keyword">while</span> nums[i] != i+<span class="hljs-number">1</span>:
                <span class="hljs-comment">#print(f"i={i} nums[i]-1={nums[i]-1} nums={nums}")</span>
                <span class="hljs-keyword">if</span> nums[i] == nums[nums[i]<span class="hljs-number">-1</span>]:
                    ans[<span class="hljs-number">0</span>] = nums[i]
                    <span class="hljs-keyword">break</span>
                <span class="hljs-comment"># 注意，这里有个大坑。最开始写成了  nums[i], nums[nums[i]-1] = nums[nums[i]-1] , nums[i]， 是不对的！</span>
                <span class="hljs-comment"># 必须用一个中间变量t2来交换</span>
                t2 = nums[i] - <span class="hljs-number">1</span>
                nums[i], nums[t2] = nums[t2], nums[i]
            i += <span class="hljs-number">1</span>
        
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(len_nums):
            <span class="hljs-keyword">if</span> nums[i] != i+<span class="hljs-number">1</span>:
                ans[<span class="hljs-number">1</span>] = i+<span class="hljs-number">1</span>
                <span class="hljs-keyword">break</span>
        <span class="hljs-keyword">return</span> ans
</div></code></pre>
<h1 id="7-lc-169-majority-element-出现次数--n2">7.  LC 169. Majority Element    出现次数 &gt; n/2</h1>
<p><a href="https://leetcode.com/problems/majority-element/solution/">https://leetcode.com/problems/majority-element/solution/</a></p>
<p>sorting</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">majorityElement</span><span class="hljs-params">(self, nums)</span>:</span>
        nums.sort()
        <span class="hljs-keyword">return</span> nums[len(nums)//<span class="hljs-number">2</span>]
</div></code></pre>
<p>Divide and Conquer</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">majorityElement</span><span class="hljs-params">(self, nums, lo=<span class="hljs-number">0</span>, hi=None)</span>:</span>
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">majority_element_rec</span><span class="hljs-params">(lo, hi)</span>:</span>
            <span class="hljs-comment"># base case; the only element in an array of size 1 is the majority</span>
            <span class="hljs-comment"># element.</span>
            <span class="hljs-keyword">if</span> lo == hi:
                <span class="hljs-keyword">return</span> nums[lo]

            <span class="hljs-comment"># recurse on left and right halves of this slice.</span>
            mid = (hi-lo)//<span class="hljs-number">2</span> + lo
            left = majority_element_rec(lo, mid)
            right = majority_element_rec(mid+<span class="hljs-number">1</span>, hi)

            <span class="hljs-comment"># if the two halves agree on the majority element, return it.</span>
            <span class="hljs-keyword">if</span> left == right:
                <span class="hljs-keyword">return</span> left

            <span class="hljs-comment"># otherwise, count each element and return the "winner".</span>
            left_count = sum(<span class="hljs-number">1</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(lo, hi+<span class="hljs-number">1</span>) <span class="hljs-keyword">if</span> nums[i] == left)
            right_count = sum(<span class="hljs-number">1</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(lo, hi+<span class="hljs-number">1</span>) <span class="hljs-keyword">if</span> nums[i] == right)

            <span class="hljs-keyword">return</span> left <span class="hljs-keyword">if</span> left_count &gt; right_count <span class="hljs-keyword">else</span> right

        <span class="hljs-keyword">return</span> majority_element_rec(<span class="hljs-number">0</span>, len(nums)<span class="hljs-number">-1</span>)

</div></code></pre>
<p>Boyer-Moore Voting Algorithm</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">majorityElement</span><span class="hljs-params">(self, nums: List[int])</span> -&gt; int:</span>
        major_e = <span class="hljs-number">-1</span>
        major_n = <span class="hljs-number">0</span>
        <span class="hljs-keyword">for</span> num <span class="hljs-keyword">in</span> nums:
            <span class="hljs-keyword">if</span> major_n == <span class="hljs-number">0</span>:
                major_e = num
                major_n = <span class="hljs-number">1</span>
            <span class="hljs-keyword">else</span>:
                <span class="hljs-keyword">if</span> major_e == num:
                    major_n += <span class="hljs-number">1</span>
                <span class="hljs-keyword">else</span>:
                    major_n -= <span class="hljs-number">1</span>
                    
        <span class="hljs-keyword">return</span> major_e
</div></code></pre>
<h1 id="8-lc-229-majority-element-ii-出现次数--n3">8. LC 229. Majority Element II   出现次数 &gt; n/3</h1>
<ul>
<li><a href="https://leetcode.com/problems/majority-element-ii/">https://leetcode.com/problems/majority-element-ii/</a></li>
</ul>
<p>Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.</p>
<p>Note: The algorithm should run in linear time and in O(1) space.</p>
<p>Example 1:</p>
<pre><code><code><div>Input: [3,2,3]
Output: [3]
Example 2:

Input: [1,1,1,3,3,2,2,2]
Output: [1,2]
</div></code></code></pre>
<p>我的解法，先排序再查找， 时间复杂度 O(nlgn)</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">majorityElement</span><span class="hljs-params">(self, nums: List[int])</span> -&gt; List[int]:</span>
        ans = []
        <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> nums:
            <span class="hljs-keyword">return</span> ans
        nums.sort()
        level = len(nums) // <span class="hljs-number">3</span>
        nums.append(float(<span class="hljs-string">'inf'</span>))
        n = len(nums)
        e = nums[<span class="hljs-number">0</span>]
        e_num = <span class="hljs-number">1</span>
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, n):
            <span class="hljs-keyword">if</span> nums[i] == e:
                e_num += <span class="hljs-number">1</span>
            <span class="hljs-keyword">else</span>:
                <span class="hljs-comment">#print(f"{e_num}")</span>
                <span class="hljs-keyword">if</span> e_num &gt; level:
                    ans.append(e)
                e = nums[i]
                e_num = <span class="hljs-number">1</span>
        <span class="hljs-keyword">return</span> ans
</div></code></pre>
<p>别人的一个解法，应该符合条件, O(n). 但是不容易想到。</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">majorityElement</span><span class="hljs-params">(self, nums: List[int])</span> -&gt; List[int]:</span>
        candidate1, candidate2 = <span class="hljs-literal">None</span>, <span class="hljs-literal">None</span>
        count1, count2 =<span class="hljs-number">0</span>, <span class="hljs-number">0</span>
        <span class="hljs-keyword">for</span> c <span class="hljs-keyword">in</span> nums:
            <span class="hljs-keyword">if</span> c == candidate1:
                count1 += <span class="hljs-number">1</span>
            <span class="hljs-keyword">elif</span> c == candidate2:
                count2 += <span class="hljs-number">1</span>
            <span class="hljs-keyword">elif</span> count1 == <span class="hljs-number">0</span>: <span class="hljs-comment">#if the count of one candidate can reach 0, that means it is surely not more than n/3 times in the nums</span>
                candidate1 = c
                count1 = <span class="hljs-number">1</span>
            <span class="hljs-keyword">elif</span> count2 == <span class="hljs-number">0</span>:
                candidate2 = c
                count2 = <span class="hljs-number">1</span>
            <span class="hljs-keyword">else</span>:
                count1 -= <span class="hljs-number">1</span>
                count2 -= <span class="hljs-number">1</span>
        <span class="hljs-keyword">return</span> [c <span class="hljs-keyword">for</span> c <span class="hljs-keyword">in</span> (candidate1, candidate2) <span class="hljs-keyword">if</span> nums.count(c) &gt; len(nums)//<span class="hljs-number">3</span>]
</div></code></pre>

    </body>
    </html>